package cn.handong.tool.algorithm;

import java.util.ArrayList;

public class Dijkstra {
    private static int INF = Integer.MAX_VALUE;  // 代表正无穷

    /**
     * 使用Dijkstra算法计算从起点到终点的最短路径
     *
     * @param graph 图的邻接矩阵
     * @param start 起点
     * @param end   终点
     * @return 返回从起点到终点的最短路径
     */
    public static ArrayList<Integer> dijkstra(int[][] graph, int start, int end) {
        int n = graph.length;  // 图的大小

        // 初始化距离表
        int[] distance = new int[n];
        for (int i = 0; i < n; i++) {
            distance[i] = INF;
        }
        distance[start] = 0;

        // 初始化访问表
        boolean[] visited = new boolean[n];

        // 初始化路径表
        int[] path = new int[n];
        for (int i = 0; i < n; i++) {
            path[i] = start;
        }

        // 开始遍历
        for (int i = 0; i < n; i++) {
            int minDist = INF;
            int u = -1;

            // 从未访问过的节点中找到距离起点最近的节点
            for (int j = 0; j < n; j++) {
                if (!visited[j] && distance[j] < minDist) {
                    minDist = distance[j];
                    u = j;
                }
            }

            // 标记u节点已访问
            visited[u] = true;

            // 更新所有出边节点的距离表和路径表
            for (int v = 0; v < n; v++) {
                if (graph[u][v] != INF && !visited[v]) {
                    int newDist = minDist + graph[u][v];
                    if (newDist < distance[v]) {
                        distance[v] = newDist;
                        path[v] = u;
                    }
                }
            }
        }

        // 构造路径
        ArrayList<Integer> shortestPath = new ArrayList<>();
        int p = end;
        while (p != start) {
            shortestPath.add(0, p);  // 将节点放在列表头部
            p = path[p];
        }
        shortestPath.add(0, start);

        return shortestPath;
    }

    public static void main(String[] args) {
        int[][] graph = {
                // 邻接矩阵表示有向带权图
                {0, 7, 9, INF, INF, 14},
                {7, 0, 10, 15, INF, INF},
                {9, 10, 0, 11, INF, 2},
                {INF, 15, 11, 0, 6, INF},
                {INF, INF, INF, 6, 0, 9},
                {14, INF, 2, INF, 9, 0}
        };
        int start = 0;
        int end = 4;

        ArrayList<Integer> shortestPath = dijkstra(graph, start, end);
        System.out.println("从节点" + start + "到节点" + end + "的最短路径为：" + shortestPath);
    }
}